package com.kehao.leetcode.hard.array;

import org.junit.Test;

import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;
import java.util.PriorityQueue;

public class MaxSlidingWindow {
    //这个方法是O(n^2) 会超时
    public int[] maxSlidingWindow01(int[] nums, int k) {
        if(nums==null) return nums;
        int[] result = new int[nums.length-k+1];
        int max = Integer.MIN_VALUE;
        int pos = -1;
        for (int start = 0; start < result.length; start++) {
            int end = start+k-1;
            if(pos<start){
                max = Integer.MIN_VALUE;
                for (int i = start; i <= end; i++) {
                    if(nums[i]>max){
                        max = nums[i];
                        pos = i;
                    }
                }
            }else if(max<nums[end]){
                max = nums[end];
                pos = end;
            }
            result[start] = max;
        }
        return result;
    }

    //优先队列的方法
    public int[] maxSlidingWindow02(int[] nums, int k) {
        int[] result = new int[nums.length-k+1];
        PriorityQueue<int[]> priorityQueue = new PriorityQueue<>((num1,num2)->num2[0]-num1[0]);
        for (int i = 0; i < k-1; i++) {
            priorityQueue.add(new int[]{nums[i],i});
        }
        for (int start = 0; start < result.length; start++) {
            int end = start+k-1;
            priorityQueue.add(new int[]{nums[end],end});
            while (!priorityQueue.isEmpty()){
                int[] peek = priorityQueue.peek();
                if(peek[1]>=start){
                    result[start] = peek[0];
                    break;
                }else {
                    priorityQueue.poll();
                }
            }
        }
        return result;
    }

    //继续优化使得 在优先队列内下标对应的元素是严格递进的
    public int[] maxSlidingWindow(int[] nums, int k) {
        int[] result = new int[nums.length-k+1];
        Deque<Integer> deque = new LinkedList<>();
        for (int i = 0; i < k-1; i++) {
            while (!deque.isEmpty()&&nums[deque.peekLast()]<=nums[i]){
                deque.pollLast();
            }
            deque.offerLast(i);
        }
        for (int start = 0; start < result.length; start++) {
            int end = start+k-1;
            while (!deque.isEmpty()&&nums[deque.peekLast()]<=nums[end]){
                deque.pollLast();
            }
            deque.offerLast(end);
            while (deque.peekFirst()<start) deque.pollFirst();
            result[start] = nums[deque.peekFirst()];
        }
        return result;
    }

    @Test
    public void test01(){
//        输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
//        输出：[3,3,5,5,6,7]
        int[] nums ={1,3,-1,-3,5,3,6,7};
        int k = 3;
        int[] result = maxSlidingWindow(nums, k);
        Arrays.stream(result).forEach(i-> System.out.print(i+" "));
    }

    @Test
    public void test02(){
//        输入：nums = [1], k = 1
//        输出：[1]
        int[] nums ={1};
        int k = 1;
        int[] result = maxSlidingWindow(nums, k);
        Arrays.stream(result).forEach(i-> System.out.print(i+" "));
    }

    @Test
    public void test03(){
//        输入：nums = [1,-1], k = 1
//        输出：[1,-1]
        int[] nums ={1,-1};
        int k = 1;
        int[] result = maxSlidingWindow(nums, k);
        Arrays.stream(result).forEach(i-> System.out.print(i+" "));
    }

    @Test
    public void test04(){
//        输入：nums = [9,11], k = 2
//        输出：[11]
        int[] nums ={9,11};
        int k = 2;
        int[] result = maxSlidingWindow(nums, k);
        Arrays.stream(result).forEach(i-> System.out.print(i+" "));
    }

    @Test
    public void test05(){
//        输入：nums = [4,-2], k = 2
//        输出：[4]
        int[] nums ={4,-2};
        int k = 2;
        int[] result = maxSlidingWindow(nums, k);
        Arrays.stream(result).forEach(i-> System.out.print(i+" "));
    }


    @Test
    public void test06(){
//        输入：nums = [4,-2], k = 2
//        输出：[4]
        int[] nums ={7,2,4};
        int k = 2;
        int[] result = maxSlidingWindow(nums, k);
        Arrays.stream(result).forEach(i-> System.out.print(i+" "));
    }
}
